// GLOBAL REDUNDANCY ELIMINATION FUNCTIONS
void add_expr_to_list(struct BB* block, struct expression_tan *expr)
{
	struct expression_tan *temp = block->exprList;
	if (temp == NULL) block->exprList = expr;
	else {
		while (temp->next != NULL) {
			temp = temp->next;
		}
		temp->next = expr;
	}
}

void remove_expr_from_list(struct BB *block, struct expression_tan *expr)
{
	struct expression_tan *temp = block->exprList;
	if (temp == NULL) return;
	if (temp->hash == expr->hash) {
		// If the expression is the first in the list, point to the next one and free memory
		block->exprList = temp->next;
		free(temp);
	} else {
		// The expression is elsewhere in the list, so find it and delete it
		while (temp->next != NULL && temp->next->hash != expr->hash) {
			temp = temp->next;
		}
		if (temp->next == NULL) return;
		// The next expression has the desired hash - remove it!
		struct expression_tan *next = temp->next;
		temp->next = next->next;
		free(next);
	}
}

struct expression_tan *new_expression_tan(char *expr, int LHS, int hash)
{
	struct expression_tan *newExpr = (struct expression_tan *)(malloc(sizeof(struct expression_tan)));
	newExpr->expr = expr;
	newExpr->LHS = LHS;
	newExpr->hash = hash;
	newExpr->next = NULL;
	newExpr->countRHS = 0;
	newExpr->countLines = 0;
	return newExpr;
}

int is_key_in_rhs(struct expression_tan *expr, int key)
{
	int i;
	for (i = 0; i < expr->countRHS; i++) {
		if (expr->RHS[i] == key) return 1;
	}
	return 0;
}

void copy_global_expr_rhs(int *to)
{
	int i;
	for (i = 0; i < exprRHSCount; i++) {
		*(to + i) = exprRHS[i]; 
	}
}

void add_key_to_global_rhs(int key)
{
	if (cfg_symtab_is_userdef(key) == 1) {
		exprRHS[exprRHSCount] = key;
		exprRHSCount++;
	}
}

void add_line_number_to_expr(struct expression_tan *expr, int line)
{
	expr->Lines[expr->countLines] = line;
	expr->countLines++;
}

struct expression_tan *lookup_expression(struct BB *bb, struct expression_tan *expr)
{
	struct expression_tan *temp = bb->exprList;
	while (temp != NULL) {
		if (temp->hash == expr->hash) {
			return temp;
		}
		temp = temp->next;
	}
	return NULL;
}

char *get_expr_var_name(int hash)
{
	char *name = (char *)(malloc(32*sizeof(char)));
	strcpy(name, "expr.");
	strcat(name, inttostring(hash));
	return name;
}

void remove_all_expr_with_key(int key, struct BB *bb)
{
	if (bb->exprList == NULL) return;
	if (is_key_in_rhs(bb->exprList, key) == 1) {
		// The first expression in the block matches this, so remove it and call the function again with the new expression list
		struct expression_tan *first = bb->exprList;
		bb->exprList = first->next;
		free(first);
		remove_all_expr_with_key(key, bb);
	} else {
		struct expression_tan *temp = bb->exprList;
		while (temp->next != NULL) {
			if (is_key_in_rhs(temp->next, key) == 1) {
				struct expression_tan *next = temp->next;
				temp->next = next->next;
				free(next);
			} else {
				temp = temp->next;
			}
		}
	}
}

void print_gtemp ()
{
	struct gtempTbl * temp = tempReplace;
	while (temp != NULL)
	{
		printf("Replace LHS of linenumber %d or rhs with op val %d(%s) with %d (%s) \n", temp->line, temp->val, cfg_symtab_get_val (temp->val),temp->tempKey, cfg_symtab_get_val (temp->tempKey));
		temp = temp->next;
	}
}

void add_to_gtemp (int line, int val, int type, int tempKey)
{
	struct gtempTbl *temp = malloc(sizeof(struct gtempTbl));
	temp->line = line;
	temp->val = val;
	temp->tempKey = tempKey;
	temp->next = tempReplace;
	temp->type = type;
	tempReplace = temp;
}

void add_temp_to_replace (struct expression_tan * exprList, struct expression_tan * expr, int replace)
{
       struct expression_tan * tempExpr = exprList;
       int count = 1;
       while (tempExpr != NULL)
           {
           //printf("Final list %d %d %d \n", tempExpr->LHS, tempExpr->hash, expr->hash);
           if (tempExpr->hash == expr->hash)
               {
               while (count < tempExpr->countLines)
                   {
                   add_to_gtemp (tempExpr->Lines[count], -1, 0, replace);
                   count++;
                   printf("GTEMP %d %d \n", tempReplace->line, tempReplace->tempKey);
                   }
               }
           tempExpr = tempExpr->next;
           }       
} 

void gre_evaluate_node(struct Three_AddressNode *node, struct BB *bb) 
{
	// We only want to evaluate assignment nodes
	if (node->type != THREE_ADDRESS_ASSIGN) return;

	// Check to see if the operands are in the replacement table and replace them if they are
	struct replaceTable *replace;
	if (node->operand1) {
		replace = lookupGlobalReplacement(node->operand1);
		if (replace != NULL) node->operand1 = replace->replace;
	}
	if (node->operand2) {
		replace = lookupGlobalReplacement(node->operand2);
		if (replace != NULL) node->operand2 = replace->replace;
	}

	struct cfg_symtab_elem *lhsVar = cfg_symtab_lookup(node->LHS);

	// Check to see if the expression is in the list already
	struct expression_tan *existing = lookup_expression(bb, node->expr);
	if (existing != NULL) {
		// The expression is in the list already, and thus variables can be replaced
		// First, get the key for the expression variable that will replace the node's RHS
		char *exprVarName = get_expr_var_name(node->expr->hash);
		int exprKey = makekey(exprVarName, MAX_VARIABLES);

		// If the variable is not in the symbol table yet, add it
		struct cfg_symtab_elem *exprVar = cfg_symtab_lookup(exprKey);
		if (exprVar == NULL) {
			// The variable is not in the symbol table yet - add it
			cfg_symtab_add(SYM_TYPE_TEMP, exprKey, exprVarName);
		}

		if (lhsVar->type == SYM_TYPE_TEMP) {
			// The LHS is a temporary variable - replace it with the expression variable
			add_to_global_replace(node->LHS, exprKey);

			// The statement is no longer needed - remove it from the CFG
			node->delFlag = 1;
		}
	}

	if (lhsVar->type == SYM_TYPE_USER) {
		// The LHS is user-defined - so remove all expressions that have the LHS in their RHS
		remove_all_expr_with_key(node->LHS, bb);
	}

	if (existing == NULL) {
		// The expression is not in the list yet - add it
		copy_expr_to(node->expr, bb);
	}
}

void gre_evaluate_block(struct BB *bb) 
{
	struct Three_AddressNode *temp = bb->entry;
	gre_evaluate_node(temp, bb);
	bb->marked = 1;
	if (temp->delFlag == 1) 
	{
		// Entry point treated differently than the rest of the nodes - if the entry is set for deletion, delete it and re-call the evaluation
		bb->entry = temp->next;
		remove_from_node_list(temp);
		free(temp);
		gre_evaluate_block(bb);
	}
	else {
		// Otherwise, proceed with evaluating the rest of the nodes in the block
		while (temp->next != NULL)
		{
			//printf("\nEVALUATING***********************\n");
			//print_three_address(temp->next);
			//printf("\n*********************************\n");
			struct Three_AddressNode *next = temp->next;
			gre_evaluate_node(next, bb);
			if (next->delFlag == 1)
			{
				//printf("\nTHIS IS BEING DELETED***********************\n");
				struct nvgOperand * op1 = getOperand(next->LHS, bb, next);
				struct replaceTable *replace = lookupGlobalReplacement(next->LHS);
				add_temp_to_replace (bb->exprList, next->expr, replace->replace);
				//print_three_address(next);
				//printf("\n******************************************\n");
				temp->next = next->next;
				remove_from_node_list(next);
				free(next);
			} else {
				temp = temp->next;
			}
			//printf("\nNEXT UP:\n");
			//if (temp->next != NULL) print_three_address(temp->next);
			//printf("*****************************************\n");
		}
	}
}

int get_if_exists_gtemp (int key, int type)
{
	struct gtempTbl *temp = tempReplace;
	while (temp != NULL)
	{                
		if (type==0 && temp->line == key)
			return temp->tempKey;

		if (type==1 && temp->val == key)
			return temp->tempKey;

		temp = temp->next;
	}
	return -1;
}

void global_redundancy_elim2 (struct BB *block)
{
	struct BB *bb = block;
	int replaceLHS = -1;
	int tempLHS;
	if (block == NULL || block->marked==1) return;

	block->marked = 1;

	struct Three_AddressNode * node = block->entry;
	while (node != NULL)
	{

		if ((replaceLHS = get_if_exists_gtemp (node->operand1, 1)) != -1)
			node->operand1 = replaceLHS;

		if ((replaceLHS = get_if_exists_gtemp (node->operand2, 1)) != -1)
			node->operand2 = replaceLHS;

		if ((replaceLHS = get_if_exists_gtemp (node->lineNumber, 0)) != -1)
		{
			tempLHS = node->LHS; 
			node->LHS = replaceLHS;
			add_to_gtemp (-1, tempLHS, 1, replaceLHS);
		}

		if (node->next && node==node->next)
			break;

		node = node->next;            
	}        

	if (bb->exit && bb->exit->ptr1 != NULL)
		global_redundancy_elim2 (bb->exit->ptr1);

	if (bb->exit && bb->exit->ptr2 != NULL)
		global_redundancy_elim2 (bb->exit->ptr2);
}

void global_redundancy_elim (struct CFG * cfg)
{
	if (cfg->entry == NULL) return;
	struct BB* curBB = cfg->entry;
	gre_evaluate_blocks(curBB, 1);
}

struct BB * gre_evaluate_blocks(struct BB* bb, int force)
{
	struct Three_AddressNode *exitNodeOfBlock = bb->exit;
	struct BB * dummy1 = NULL;
	struct BB * dummy2 = NULL;

	/* if current block is pointing to dummy, then return */
	// If force is passed, then we have printed all of the parents of the dummy and can now print the dummy itself
	if ((bb->parentCount > 1 || bb->marked == 1) && force == 0) 
	{
		// Having a marked block in this case means we are visiting the while loop conditional block
		if (bb->marked == 1) return NULL;
		return bb;
	}


	/* initialize gre with parent */
	gre_init_with_parent(bb);

	// We do not want to evaluate the while condition statement
	if (bb->type != BB_TYPE_WHILE_COND) {
		/* evaluate the current block */
		gre_evaluate_block(bb);
	}

	/* recursive call to evaluate next block */
	if (exitNodeOfBlock->ptr1!=NULL)
		dummy1 = gre_evaluate_blocks(exitNodeOfBlock->ptr1, 0);

	if (exitNodeOfBlock->ptr2!=NULL)
		dummy2 = gre_evaluate_blocks(exitNodeOfBlock->ptr2, 0);

	/* check if they are pointing to dummies */
	if (dummy1 != NULL && dummy2 != NULL)
	{
		return gre_evaluate_blocks (dummy2, 1);
	}
	else if (dummy1 != NULL) return dummy1;
	else if (dummy2 != NULL) return dummy2;

	return NULL;      
}

void gre_init_with_parent (struct BB *bb)
{
	struct expression_tan * parent1, * parent2;
	if (bb->parentCount == 1)
	{
		parent1 = bb->parents->parent->exprList;
		while (parent1 != NULL)
		{
			copy_expr_to(parent1, bb);
			parent1 = parent1->next;
		}
	}
	else if (bb->parentCount == 2)
	{
		//printf("***** bb num %d, parent1 %d , parent2 %d ****** \n", bb->number, bb->parents->parent->number, bb->parents->nextparent->parent->number); 
		parent1 = bb->parents->parent->exprList;
		while (parent1 != NULL)
		{
			parent2 = bb->parents->nextparent->parent->exprList;
			while (parent2 != NULL)
			{
				//                                      printf("%d-%d, %d-%d \n", parent1->lhs, parent1->rhs,parent2->lhs, parent2->rhs);
				if (((parent1->hash) && (parent2->hash) && (parent1->hash==parent2->hash)))
				{
					struct expression_tan *newNode = copy_expr_to(parent1, bb);
					expr_combine_lines(newNode, parent1, parent2);
				}
				parent2 = parent2->next;
			}
			parent1 = parent1->next;
		} 
	}
	return;
}

void expr_combine_lines(struct expression_tan *newNode, struct expression_tan *parent1, struct expression_tan *parent2)
{
	int i;
	for (i = 0; i < parent1->countLines; i++) {
		add_line_number_to_expr(newNode, parent1->Lines[i]);
	}	
	for (i = 0; i < parent2->countLines; i++) {
		add_line_number_to_expr(newNode, parent2->Lines[i]);
	}
}

struct expression_tan *copy_expr_to(struct expression_tan *expr, struct BB *block)
{
	struct expression_tan *newExpr = new_expression_tan(expr->expr, expr->LHS, expr->hash);
	copy_expr_rhs(expr, newExpr);
	copy_expr_lines(expr, newExpr);
	add_expr_to_list(block, newExpr);
	return newExpr;
}

void copy_expr_rhs(struct expression_tan *from, struct expression_tan *to)
{
	to->countRHS = from->countRHS;
	int i;
	for (i = 0; i < from->countRHS; i++) {
		to->RHS[i] = from->RHS[i];
	}
}

void copy_expr_lines(struct expression_tan *from, struct expression_tan *to) 
{
	to->countLines = from->countLines;
	int i;
	for (i = 0; i < from->countLines; i++) {
		to->Lines[i] = from->Lines[i];
	}
}

void add_to_global_replace (int del, int rel) 
{
	// Create the new replacement rule
	struct replaceTable *newReplace = (struct replaceTable *)(malloc(sizeof(struct replaceTable)));
	newReplace->del = del;
	newReplace->replace = rel;
	newReplace->next = NULL;

	// Add rule to nvg
	if (globalReplace == NULL) {
		globalReplace = newReplace;
	} else {
		struct replaceTable *bbRep = globalReplace;
		while (bbRep->next != NULL) {
			bbRep = bbRep->next;
		}
		bbRep->next = newReplace;
	}
}

struct replaceTable *lookupGlobalReplacement(int del)
{
	struct replaceTable *temp = globalReplace;
	while (temp != NULL) 
	{
		if (temp->del == del) {
			return temp;
		}
		temp = temp->next;
	}
	return NULL;
}

